import java.util.Arrays;

public class Demo1 {
    public static void main(String[] args) {

    }
}

class Solution {
    public int[] numberGame(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] arr = new int[n];

        int j = 0;
        for(int i = 0;i < n;){
            int a = nums[i++];
            int b = nums[i++];
            arr[j++] = b;
            arr[j++] = a;
        }

        return arr;
    }
}

class Solution {
    public int maxBottlesDrunk(int numBottles, int numExchange) {
        // 增加了一个条件就是每次喝完一瓶水,需要增加一个交换的空水瓶
        int kong = numBottles;
        int jh = numExchange;
        int count = kong;

        while(kong >= jh){
            count += 1;
            kong = kong - jh + 1;
            jh++;
        }

        return count;
    }
}

class Solution {
    public int brokenCalc(int startValue, int target) {
        int count = 0;

        // 1000 4 < 5 1
        while(target > startValue){
            if((target & 1) == 0){
                target /= 2;
            }else{
                target += 1;
            }
            count++;
        }
        // 上次存储的startValue是小于target的
        // 说明startValue需要减去诺干个1,再乘2就可以得到target
        count += startValue - target;

        return count;
    }
}

class Solution {
    public int alternatingSum(int[] nums) {
        int n = nums.length;
        int sum1 = 0,sum2 = 0;

        for(int i = 0;i < n;i++)
        {
            if(i % 2 == 0) sum1 += nums[i];
            else sum2 += nums[i];
        }

        return sum1 - sum2;
    }
}

class MedianFinder {
    PriorityQueue<Integer> pq1;
    PriorityQueue<Integer> pq2;
    public MedianFinder() {
        pq1 = new PriorityQueue<>((a,b)->b - a);
        pq2 = new PriorityQueue<>((a,b)->a - b);
    }

    public void addNum(int num) {
        int m = pq1.size();
        int n = pq2.size();
        int top1 = 0,top2 = 0;
        if(m != 0)
            top1 = pq1.peek();
        if(n != 0)
            top2 = pq2.peek();

        if(m == n)
        {
            if(m == 0 || num <= top1)
            {
                pq1.add(num);
            }
            else if(num > top1)
            {
                // n + 1
                pq2.add(num);
                int k = pq2.peek();
                pq2.poll();
                pq1.add(k);
            }
        }
        else if(m > n) // m == n + 1
        {
            if(num <= top1)
            {
                // m == n + 2
                pq1.add(num);
                int k = pq1.peek();
                pq1.poll();
                pq2.add(k);
            }
            else // num > top1
            {
                pq2.add(num);
            }
        }
    }

    public double findMedian() {
        int sum = pq1.size() + pq2.size();
        if(sum % 2 == 0)
        {
            return (pq1.peek() + pq2.peek()) / 2.0;
        }
        else
        {
            return pq1.peek();
        }
    }
}

class Solution {
    public:
    int dx[4] = {0,0,-1,1};
    int dy[4] = {-1,1,0,0};
    bool vis[310][310] = {false};
    int count = 0;
    int m,n;
    int numIslands(vector<vector<char>>& grid) {
        // bfs
        m = grid.size();
        n = grid[0].size();

        queue<pair<int,int>> q;
        for(int i = 0;i < m;i++)
        {
            for(int j = 0;j < n;j++)
            {
                // 细节:如果是1并且是false的让它进来
                // 如果不标记为false让它进来这个条件
                // 那么有可能会重复走某个格子
                if(grid[i][j] == '1' && vis[i][j] == false)
                {
                    vis[i][j] = true;
                    bfs(grid,q,i,j);
                    // 标记完所有的格子就一个联通块
                    count++;
                }
            }
        }

        return count;
    }

    void bfs(vector<vector<char>>& grid,queue<pair<int,int>> q,int a,int b)
    {
        q.push({a,b});
        while(!q.empty())
        {
            pair<int,int> tmp = q.front();
            q.pop();
            a = tmp.first,b = tmp.second;

            for(int i = 0;i < 4;i++)
            {
                int x = dx[i] + a;
                int y = dy[i] + b;

                if(x >= 0 && x < m && y >= 0 && y < n && vis[x][y] == false && grid[x][y] == '1')
                {
                    q.push({x,y});
                    vis[x][y] = true;
                }
            }
        }
    }
};

class Solution {
    int dx[] = {0,0,-1,1};
    int dy[] = {-1,1,0,0};
    boolean[][] vis = new boolean[60][60];
    int m,n;
    int mx = 0;// 最大的那块陆地的大小
    int count = 0;// 统计每块陆地的个数
    public int maxAreaOfIsland(int[][] grid) {
        m = grid.length;
        n = grid[0].length;

        for(int i = 0;i < m;i++)
        {
            for(int j = 0;j < n;j++)
            {
                if(!vis[i][j] && grid[i][j] == 1)
                {
                    vis[i][j] = true;
                    // 刚进来的这个点也要加上
                    // 可能会忘记加上
                    count++;
                    bfs(i,j,grid);
                    mx = Math.max(mx,count);
                    count = 0;
                }
            }
        }

        return mx;
    }

    void bfs(int a,int b,int[][] grid)
    {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{a,b});
        while(!q.isEmpty())
        {
            int[] tmp = q.poll();
            a = tmp[0];
            b = tmp[1];
            for(int k = 0;k < 4;k++)
            {
                int x = dx[k] + a;
                int y = dy[k] + b;
                if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1)
                {
                    vis[x][y] = true;
                    count++;
                    q.add(new int[]{x,y});
                }
            }
        }
    }
}

class Solution {
    public int minElement(int[] nums) {
        int n = nums.length;
        int mi = Integer.MAX_VALUE;

        for(int i = 0;i < n;i++)
        {
            int val = nums[i];
            int sum = 0;
            while(val != 0)
            {
                sum += val % 10;
                val /= 10;
            }
            if(sum < mi) mi = sum;
        }

        return mi;
    }
}



import java.util.*;

public class Solution {
    public int[] findFluctuations (int[] memoryUsage, int k) {
        int i = 0,j = k - 1;
        int mi = Integer.MAX_VALUE;
        int mx = Integer.MIN_VALUE;
        int length = memoryUsage.length;
        int[] arr = new int[length - k + 1];
        int ii = 0;
        // j - i + 1 等于 k就是窗口的大小
        while(j < length){
            mi = Integer.MAX_VALUE;
            mx = Integer.MIN_VALUE;
            for(int p = i;p <= j;p++){
                mi = Math.min(mi,memoryUsage[p]);
                mx = Math.max(mx,memoryUsage[p]);
            }
            j++;
            i++;
            arr[ii] = mx - mi;
            ii++;
        }

        return arr;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int mi = Integer.MAX_VALUE;
    // 求树的高度
    int func(TreeNode root)
    {
        if(root == null) return 0;
        // 分为三种情况:
        // 1. 是根节点,左右孩子都为空,高度为1
        if(root.left == null && root.right == null) return 1;

        int left = func(root.left);
        int right = func(root.right);
        // 2. 左右孩子只要一个为空,说明left和right中必然有一个为0
        //    返回 left + right + 1
        if(root.left == null || root.right == null)
            return left + right + 1;

        // 3. 左右孩子都不为空,返回低的那个+1
        return left < right ? left + 1 : right + 1;
    }
    public int minDepth(TreeNode root) {
        return func(root);
    }
}


class Solution {
    public int calculate(String s) {
        int x = 1,y = 0;
        for(int i = 0;i < s.length();i++){
            char ch = s.charAt(i);
            if(ch == 'A'){
                x = x * 2 + y;
            }else{
                y = 2 * y + x;
            }
        }

        return x + y;
    }
}

class Solution {
    public boolean isAcronym(List<String> words, String s) {
        StringBuilder ss = new StringBuilder();
        int n = words.size();

        for(int i = 0;i < n;i++){
            String t = words.get(i);
            char ch = t.charAt(0);
            ss.append(ch);
        }

        return ss.toString().equals(s);
    }
}

class Solution {
    public int reverseBits(int n) {
        int ans = 0;
        for(int i = 0;i < 32;i++){
            ans = (ans << 1) | (n & 1);
            n = n >> 1;
        }

        return ans;
    }
}

class Solution {
    public String removeTrailingZeros(String num) {
        String s = "";
        int n = num.length();
        int j = 0;
        for(int i = n - 1;i >= 0;i--){
            char ch = num.charAt(i);
            if(ch == '0'){
                ;
            }else{
                j = i;
                break;
            }
        }

        for(int i = 0;i <= j;i++){
            char ch = num.charAt(i);
            s += ch;
        }

        return s;
    }
}

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        // 先递归右子树,右子树一定是右视图
        // 再使用depth变量,记录树的深度
        // 每次遇到新的深度就是加入到数组中
        List<Integer> arr = new ArrayList<>();
        dfs(root,0,arr);

        return arr;
    }

    public void dfs(TreeNode root,int depth,List<Integer> arr){
        if(root == null) return;

        if(depth == arr.size()){
            arr.add(root.val);
        }

        dfs(root.right,depth + 1,arr);
        dfs(root.left,depth + 1,arr);
    }
}

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int x : nums){
            if(map.containsKey(x)){
                map.put(x,map.get(x) + 1);
            }else{
                map.put(x,1);
            }
        }

        // 按照出现的次数进行排序
        PriorityQueue<Map.Entry<Integer,Integer>> pq = new PriorityQueue<>(
                (a,b) -> b.getValue() - a.getValue()// 降序
        );

        // 将map的所有元素加入到堆中,然后按堆的方式进行排序
        pq.addAll(map.entrySet());
        int[] ans = new int[k];
        int j = 0;
        while(k != 0 && !pq.isEmpty()){
            Map.Entry<Integer,Integer> entry = pq.poll();
            ans[j++] = entry.getKey();
            k--;
        }

        return ans;
    }
}

import java.util.*;

public class Solution {
    int m,n;
    boolean[][] vis;
    int[] dx = {0,0,-1,1};
    int[] dy = {-1,1,0,0};
    public int rotApple (ArrayList<ArrayList<Integer>> grid) {
        m = grid.size();
        n = grid.get(0).size();
        vis = new boolean[m][n];

        // 把腐烂的苹果都放到一个队列中
        Queue<int[]> q = new LinkedList<>();
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(grid.get(i).get(j) == 2){
                    q.add(new int[]{i,j});
                }
            }
        }
        // 2 1 1
        // 1 0 1
        // 1 1 1
        int time = 0;
        while(!q.isEmpty()){
            int sz = q.size();
            for(int i = 0;i < sz;i++){
                int[] tmp = q.poll();
                int a = tmp[0];
                int b = tmp[1];

                for(int k = 0;k < 4;k++){
                    int x = dx[k] + a;
                    int y = dy[k] + b;
                    if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid.get(x).get(y) == 1){
                        vis[x][y] = true;
                        q.add(new int[]{x,y});
                    }
                }
            }
            time++;
        }

        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(grid.get(i).get(j) == 1 && !vis[i][j]){
                    return -1;
                }
            }
        }

        // 最后一次感染都是腐烂的苹果，还多计算了一次
        return time - 1;
    }
}

class Solution {
    private static final String[][] C = new String[][]{
            {"","I","II","III","IV","V","VI","VII","VIII","IX"},// 个位
            {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"},// 十位
            {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"},// 百位
            {"","M","MM","MMM"}                                 // 千位
    };
    // 打表
    public String intToRoman(int num) {
        return C[3][num / 1000] + C[2][num / 100 % 10] + C[1][num / 10 % 10] + C[0][num % 10];
    }
}

class Solution {
    public int minimumOperations(int[] nums) {
        int count = 0;
        int n = nums.length;

        for(int i = 0;i < n;i++){
            if(nums[i] % 3 != 0){
                int a = nums[i] % 3;
                int b = 3 - a;
                if(a < b) count += a;
                else count += b;
            }
        }

        return count;
    }
}

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] arr = new int[m + n];

        int j = 0;
        for(int i = 0;i < m;i++){
            arr[i] = nums1[i];
        }

        for(int i = m;i < m + n;i++){
            arr[i] = nums2[j++];
        }

        Arrays.sort(arr);
        int len = arr.length;
        if(len % 2 == 0){
            return 1.0 * (arr[len / 2] + arr[len / 2 - 1]) / 2;
        }
        else{
            return 1.0 * (arr[len / 2]);
        }
    }
}


class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null) return null;

        while(head != null && head.val == val) head = head.next;
        ListNode cur;
        if(head != null)
            cur = head.next;
        else
            cur = null;

        ListNode prev = head;
        while(cur != null){
            if(cur.val == val){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }

        return head;
    }
}


class Solution {
    public:
    TreeNode* dfs(vector<int>& nums,int left,int right){
        if(left > right) return nullptr;

        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[mid]);

        // 从这个递归的参数这里,很容易看出递归的结束条件
        // 右边会一直减少1,left最终会大于右边
        // 左边会一直增加1,left最终会大于右边
        root->left = dfs(nums,left,mid - 1);
        root->right = dfs(nums,mid + 1,right);

        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return dfs(nums,0,nums.size() - 1);
    }
};


class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode node1 = new ListNode(-1);
        ListNode head1 = node1;
        ListNode node2 = new ListNode(-1);
        ListNode head2 = node2;

        ListNode cur = head;
        while(cur != null){
            if(cur.val < x){
                head1.next = new ListNode(cur.val);
                head1 = head1.next;
            }else{
                head2.next = new ListNode(cur.val);
                head2 = head2.next;
            }
            cur = cur.next;
        }

        head1.next = node2.next;

        return node1.next;
    }
}

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int left = 0,right = n - 1;
        if(n == 2){
            int sum = Math.min(height[left],height[right]);
            return sum;
        }

        int sum = 0;
        // 下标相减*min(height[left],height[right])

        while(left < right){
            sum = Math.max((right - left)*(Math.min(height[left],height[right])),sum);
            if(height[left] > height[right]){
                right--;
            }else{
                left++;
            }
        }



        return sum;
    }
}

class Solution {
    public int findNumbers(int[] nums) {
        int ans = 0;
        for(int i = 0;i < nums.length;i++){
            int val = nums[i];
            int count = 0;
            while(val != 0){
                val /= 10;
                count++;
            }
            if(count % 2 == 0) ans++;
        }

        return ans;
    }
}

class Solution {
    public int minOperations(int[] nums, int k) {
        int sum = 0;
        for(int i = 0;i < nums.length;i++){
            sum += nums[i];
        }

        return sum % k;
    }
}

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null || head.next == null) return head;
        if(head.next.next == null) return head;

        ListNode node1 = new ListNode(-1);
        node1.next = head;
        ListNode node2 = new ListNode(-1);
        node2.next = head.next;

        ListNode pev = head;
        ListNode cur = head.next;

        int i = 1;
        ListNode pprev = null;
        while(cur != null && pev != null){
            if(i % 2 == 1){
                pev.next = cur.next;
                pprev = pev;
                pev = pev.next;
            }else{
                cur.next = pev.next;
                cur = cur.next;
            }
            i++;
        }

        if(i % 2 == 1){
            pev.next = node2.next;
        }else{
            pprev.next = node2.next;
        }

        return node1.next;
    }
}